package Arrays;

public class _526_BeautifulArrangement {
    //reference
    int count = 0;

    public int countArrangement0(int N) {
        int[] nums = new int[N];
        for (int i = 1; i <= N; i++)
            nums[i - 1] = i;
        permute(nums, 0);
        return count;
    }
    public void permute(int[] nums, int l) {
        if (l == nums.length - 1) {
            int i;
            for (i = 1; i <= nums.length; i++) {
                if (nums[i - 1] % i != 0 && i % nums[i - 1] != 0)
                    break;
            }
            if (i == nums.length + 1) {
                count++;
            }
        }
        for (int i = l; i < nums.length; i++) {
            swap(nums, i, l);
            permute(nums, l + 1);
            swap(nums, i, l);
        }
    }
    public void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

    //reference solution:backtrack method
    public int countArrangement(int N) {
        boolean[] check = new boolean[N+1];
        calculate(N,1,check);
        return count;
    }

    public void calculate(int N, int pos, boolean[] check) {
        if (pos > N) {
            count++;
        }
        for(int i=1;i<=N;i++) {
            if ((!check[i]) && ((pos % i == 0) || (i % pos == 0))) {
                check[i] = true;
                calculate(N,pos+1,check);
                check[i] = false;
            }
        }
    }

    //faster reference solution
    public int countArrangement2(int N) {
        int[] a = new int[N];
        for (int i = 0; i < N; ++i) a[i] = i + 1;
        return helper(a, N);
    }

    private int helper(int[] a, int n) {
        if (n <= 0) return 1;
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] % n == 0 || n % a[i] == 0) {
                swap(a, i, n - 1);
                count += helper(a, n - 1);
                swap(a, i, n - 1);
            }
        }

        return count;
    }

}
